#include<iostream>
using namespace std;
#define M 7
#define N 6
int c[M+1][N+1];
char* X = " ABCBDAB";
char* Y = " BDCABA";

void lcs_length(){
    int i,j;
    for(i=0;i<N+1;i++)
        c[0][i] = 0;
    for(i=0;i<M+1;i++)
        c[i][0] = 0;
    for(i=1;i<=M;i++)
        for(j=1;j<=N;j++){
            if(X[i]==Y[j]){
                c[i][j] = c[i-1][j-1]+1;
            }else if(c[i-1][j] >= c[i][j-1]){
                c[i][j] = c[i-1][j];
            }else{
                c[i][j] = c[i][j-1];
            }
        }
    cout << c[M][N] << endl;
}

void print_lcs(){
    int i,j,top=0;
    char lcs_str[M];
    i = M,j=N;
    while(i>0){
        while(j>0){
            if(X[i]==Y[j]){
                cout << i<<","<<j<<":"<<X[i] <<","<< Y[j] << endl;
                i--;
                j--;
            }else if(c[i-1][j] >= c[i][j-1]){
                i--;
            }else{
                j--;
            }
        }
    if(i==0|| j==0)
        break;
    }
}

int main(){
    lcs_length();
    print_lcs();
    return 0;
}
